package l07_dynamic_planning;

/**
 * 动态规划-查询推荐-计算编辑距离
 * <p>
 * 如果i=0,j=0,那么d[i,j]=0
 * 如果i=0,j>0,那么d[i,j]=j
 * 如果i>0,j=0,那么d[i,j]=i
 * 如果i>0,j>0,那么d[i,j]=min(d[i-1,j]+1,d[j,j-1]+1,d[i-1,j-1]+r(i,j)).
 *
 * @author wangxiyue@cyou-inc.com
 * @date 2019-08-15
 * @since 1.0.0
 */
public class EditDistance {

    public static void main(String[] args) {

        System.out.println(getStrDistance("mouse", "mouuse"));
    }

    private static int getStrDistance(String a, String b) {
        if (null == a || null == b) {
            return -1;
        }

        // 初始化用于记录状态转移的二维表
        int[][] d = new int[a.length() + 1][b.length() + 1];

        // 如果i为0,且j大于等于0,,那么d[i,j]为j
        for (int j = 0; j <= b.length(); j++) {
            d[0][j] = j;
        }

        // 如果j为0,且i大于等于0,,那么d[i,j]为i
        for (int i = 0; i <= a.length(); i++) {
            d[i][0] = i;
        }

        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                int r = 0;
                if (a.charAt(i) != b.charAt(j)) {
                    r = 1;
                }

                int first_append = d[i][j + 1] + 1;
                int second_append = d[i + 1][j] + 1;
                int replace = d[i][j] + r;

                int min = Math.min(first_append, second_append);
                min = Math.min(min, replace);
                d[i + 1][j + 1] = min;
            }
        }

        return d[a.length()][b.length()];
    }

}
